/**
 * 
 */
package dp.passed2;

import java.util.Arrays;

import utils.PrintUtils;

/**
 * @author xyyi
 *
 */
public class MaximumProductSubarray {

	
	
	/**
Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
Leetcode
	 */
	//Best
	public int maxProduct1(int[] A) {
	    if (A == null || A.length == 0) {
	        return 0;
	    }
	    int max = A[0], min = A[0], result = A[0];
	    for (int i = 1; i < A.length; i++) {
	        int temp = max;
	        max = Math.max(Math.max(max * A[i], min * A[i]), A[i]);
	        min = Math.min(Math.min(temp * A[i], min * A[i]), A[i]);
	        if (max > result) {
	            result = max;
	        }
	    }
	    return result;
	}
	
    public int maxProduct2(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        if (A.length == 1)
            return A[0];
        
        int max = 0;
        int maxPositive = 0;
        int minNegative = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                maxPositive = maxPositive == 0 ? A[i] : A[i] * maxPositive;
                minNegative = minNegative == 0 ? 0 : A[i]*minNegative;
            }
            if (A[i] == 0) {
                maxPositive = 0;
                minNegative = 0;
            }
            if (A[i] < 0) {
                int copyOfMaxPositive = maxPositive;
                maxPositive = minNegative == 0 ? 0 : minNegative * A[i];
                minNegative = copyOfMaxPositive == 0 ? A[i] : copyOfMaxPositive * A[i];
            }
            max = Math.max(max, maxPositive);
        }
        
        return max;
    }
	
	
	
	/**
	 * http://uva.onlinejudge.org/external/110/11059.html
	Problem D - Maximum Product
	Time Limit: 1 second

	Given a sequence of integers S = {S1, S2, ..., Sn}, you should determine what is the value of the maximum positive product involving consecutive terms of S. If you cannot find a positive sequence, you should consider 0 as the value of the maximum product.
	Input

	Each test case starts with 1 ≤ N ≤ 18, the number of elements in a sequence. Each element Si is an integer such that -10 ≤ Si ≤ 10. Next line will have N integers, representing the value of each element in the sequence. There is a blank line after each test case. The input is terminated by end of file (EOF).
	Output

	For each test case you must print the message: Case #M: The maximum product is P., where M is the number of the test case, starting from 1, and P is the value of the maximum product. After each test case you must print a blank line.
	Sample Input

	3
	2 4 -3

	5
	2 5 -1 2 -1

	Sample Output

	Case #1: The maximum product is 8.

	Case #2: The maximum product is 20.
	
	Solution:
	http://www.youtube.com/watch?v=twaGE43dbu0
	
	globalLargetPositive = 0
	
	1 Initial state or : 
	currentLargestPositive = -1, currentLargestNegative = 1
	2 if a positive value with k
	currentLargestPositive = currentLargestPositive * k
	currentLargestNegative = currentLargestNegative * k
	  if a negative value with k
	  currentLargestPositive = currentLargestNegative * k
	  currentLargestNegative = currentLargestPositive * k
	  if a value with 0
	  currentLargestPositive = -1
	  currentLargestNegative = 1
	3 update globalLargetPositive
		if (currentLargestPositive > globalLargetPositive)
			globalLargetPositive = currentLargestPositive
	4 if currentLargestPositive < 1
		currentLargestPositive = -1
	
	 */
	public double maxSubsequentProduct(double[] numbers) {
		assert (numbers != null && numbers.length > 0);

		double maxPositive = 0;
		double currPositive = -1;
		double currNegative = 1;
		for (double number : numbers) {
			if (number > 0) {
				currPositive = currPositive == -1 ? number : currPositive
				        * number;
				currNegative = currNegative == 1 ? currNegative : currNegative
				        * number;
			} else if (number < 0) {
				if (currNegative == 1) {
					currNegative = currPositive == -1 ? number : currPositive
					        * number;
					currPositive = -1;
				} else {
					double tempPositive = currPositive;
					currPositive = currNegative * number;
					currNegative = tempPositive == -1 ? number : tempPositive
					        * number;
				}
			} else { // number == 0
				currPositive = -1;
				currNegative = 1;
			}

			maxPositive = currPositive > maxPositive ? currPositive
			        : maxPositive;

			currPositive = currPositive < 1 ? -1 : currPositive;
		}

		return maxPositive;
	}

	//http://www.geeksforgeeks.org/maximum-product-subarray/
	public int maxProduct(int[] arr) {
		if (arr == null || arr.length == 0)
			return 0;

		int max = 1;
		int maxPositive = 1; // max positive ending at current position 
		int minNegative = 1; // min negative ending at current position
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > 0) {
				maxPositive = maxPositive * arr[i];
				minNegative = Math.min(minNegative * arr[i], 1);
			} else if (arr[i] == 0) {
				maxPositive = 1;
				minNegative = 1;
			} else { // arr[i] < 0
				int tempMaxPositive = maxPositive;
				maxPositive = Math.max(minNegative * arr[i], 1);
				minNegative = tempMaxPositive * arr[i];
			}

			max = Math.max(max, maxPositive);
		}

		return max;
	}

	public int[] maxProductArray(int[] arr) {
		int max = 1, maxStart = 0, maxEnd = 0;
		int maxPos = 1, maxPosStart = -1, maxPosEnd = -1;
		int minNeg = 1, minNegStart = -1, minNegEnd = -1;

		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > 0) {
				maxPos = maxPos * arr[i];
				maxPosStart = maxPosStart == -1 ? i : maxPosStart;
				maxPosEnd = i;
				if (minNeg < 0) {
					minNeg = minNeg * arr[i];
					minNegEnd = i;
				}
			} else if (arr[i] == 0) {
				maxPos = 1;
				maxPosStart = i + 1;
				maxPosEnd = i + 1;
				minNeg = 1;
				minNegStart = i + 1;
				minNegEnd = i + 1;
			} else { // arr[i] < 0
				int tempMaxPos = maxPos, tempMaxPosStart = maxPosStart;
				if (minNeg == 1) {
					maxPos = 1;
					maxPosStart = -1;
					maxPosEnd = -1;
				} else { //minNeg < 0
					maxPos = minNeg * arr[i];
					maxPosStart = minNegStart;
					maxPosEnd = i;
				}
				minNeg = tempMaxPos * arr[i];
				minNegStart = tempMaxPosStart == -1 ? i : tempMaxPosStart;
				minNegEnd = i;
			}
			if (max < maxPos) {
				max = maxPos;
				maxStart = maxPosStart;
				maxEnd = maxPosEnd;
			}
		}

		return Arrays.copyOfRange(arr, maxStart, maxEnd + 1);
	}

	/**
	 * 
	 */
	public MaximumProductSubarray() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MaximumProductSubarray msp = new MaximumProductSubarray();
		//		double[][] numsArr = { { 0.5, -2.5, 3.0, -6 }, { -2 },
		//		        { -0.6, 0.6, -0.7, 0.8, 0.5 }, { -0.5, -0.7, -0.6 },
		//		        { 2, 5, -1, 2, -1 } };
		//		for (double[] numbers : numsArr) {
		//			for (double number : numbers) {
		//				System.out.printf("%f,", number);
		//			}
		//			System.out.printf(" max subsequent product is %f\n", msp
		//			        .maxSubsequentProduct(numbers));
		//		}

		int[][] arrInt = { { 1, 2, 3, 4 }, { 5 }, { -3, -2, 0, -1, 1, 2, -4 },
		        { -4, -2, -5 }, { -3, 5, -9, -1, -2 } };

		for (int[] numbers : arrInt) {
			PrintUtils.printArray(numbers);
			System.out.printf(" max subsequent product is %d\n", msp
			        .maxProduct(numbers));
			PrintUtils.printArray(msp.maxProductArray(numbers));
			System.out.println();
		}

	}
}
